1. Field of the Invention
Our invention relates to the field of information processing, and more specifically to rapid sorting of information stored in binary form.
2. Description of the Prior Art
Efficient sorting of data is a problem which receives considerable attention in computer science. Two sorting networks in particular have been developed which significantly advanced the state of knowledge in this area. One well known sorting network is a bitonic sorter devised by K. E. Batcher and described in "Sorting Networks and Their Application", Proc. AFIPS 1968 Spring Joint Comp. Conf.; Vol. 32, AFIPS Press, Montrale, N.J.; pp 307-314. The bitonic sorter requires (1/2) log.sub.2 N(1+log.sub.2 N) ranks of N/2 compare-exchange (CE) modules each to sort N=2.sup.k items of data. The delay, or sorting time, required is (1/2) log.sub.2 N(1+log.sub.2 N).
H. S. Stone developed a modification of the bitonic sorter in which N=2.sup.k data items could be sorted by a structure having a single rank of N storage registers and a signal rank of N/2 CE modules. This processor is illustrated and described in H. S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. Comp., Vol. C-20, No. 2, February 1971, pp 153-161. The Stone processor requires a delay of (log.sub.2 N).sup.2 -(log.sub.2 N)+1.
A drawback to Batcher's bitonic sorter is that, once built for a certain list size, it cannot be easily modified to sort longer lists. In addition, unless data is pipelined through the network, most of the CE modules are idle at any given time. Stone's processor requires fewer CE modules, all of which are used simultaneously during processing. However, all of the CE modules are idle for nearly half the total processing time, while data is being rearranged. Stone's processor is also unable to sort longer lists than that for which it was built.
Our invention is a parallel sorting processor which overcomes the above-mentioned limitations.